As is well known, a solid state drive (SSD) is a data storage device that uses a non-volatile memory to store data. A NAND-based flash memory is one kind of the non-volatile memory. After data are written to the flash memory, if the system is powered off, the data are still retained in the flash memory.
FIG. 1 is a schematic functional block diagram illustrating a conventional solid state drive. As shown in FIG. 1, the solid state drive 10 comprises a controller 101, a buffer 107 and a flash memory 105. The controller 101 is in communication with the flash memory 105 and the buffer 107. In addition, the controller 101 is in communication with a host 12 through an external bus 20. Consequently, commands and data can be exchanged between the controller 101 and the host 12.
A process of programming write data from the host 12 into the flash memory 105 will be illustrated as follows. Firstly, the controller 101 performs an error correction (ECC) encoding operation on the write data, and then temporarily stores the write data into the buffer 107. Moreover, the controller 101 performs a program action at proper time in order to store the write data of the buffer 107 into the flash memory 105.
For example, the buffer 107 is a cache memory such as a static random access memory (SRAM) or a dynamic random access memory (DRAM). Generally, the external bus 20 is a USB bus, an IEEE 1394 bus, an SATA bus, or the like.
Generally, the flash memory 105 comprises plural blocks, for example 1024 blocks. Each block comprises plural pages, for example 64 pages. Each page is typically 4K bytes in size. Due to the inherent properties of the flash memory 105, at least one page is written during the program action, and the erase operation is performed in a block-wise fashion.
Generally, the host 12 accesses the flash memory 105 through logical block addresses (LBA). Each LBA can store data of 512 bytes in size. When the host 12 intends to program the write data into the flash memory 105, the host 12 may provide a write command and a corresponding LBA to the controller 101. Then, the write data is transmitted from the host 12 to the controller 101. The write data is temporarily stored in the buffer 107 by the controller 101.
For example, if one page of the flash memory 105 is 4K bytes in size, the data amount of eight LBAs is equal to the data amount of one page. As known, the flash memory 105 is programmed in a unit of at least one page. If the amount of data temporarily stored in the buffer 107 exceeds the data amount of one page, the controller 101 starts the program action and programs the data to the flash memory 105 in a unit of at least one page.
Moreover, the controller 101 selects one free block of the flash memory 105 as an open block. While the program action is performed, the data temporarily stored in the buffer 107 is programmed into the open block under control of the controller 101. After the open block is occupied by the data, the controller 101 will select another block as another open block and continuously program the data of the buffer 107 into this open block.
Since the erase operation of the flash memory 105 is performed in a block-wise fashion, the data is each page cannot be individually erased and updated. After an updated data is received by the flash memory 105, the updated data is stored in a new page (i.e., a blank page), and the original data in the old page is set as an invalid data. However, after the flash memory 105 has been accessed for a long time, each block of the flash memory 105 may contain some valid data and some invalid data. Consequently, the writable space of the flash memory 105 gradually decreases.
FIGS. 2A˜2C schematically illustrate a process of updating data of a conventional flash memory. It is assumed that the flash memory has five blocks (Block_1˜Block_5). Each block has four pages (Page_1˜Page_4).
As shown in FIG. 2A, the first block (Block_1) stores the data Data1˜Data4, and the second block (Block_2) stores the data Data5˜Data8.
For example, the host 12 intends to output the write data Data8′, Data2′, Data9, Data10, Data11, Data7′, Data12 and Data13 to the flash memory 105. The write data Data2′, Data7′ and Data8′ are updated data of the data Data2, Data7 and Data8, respectively. The write data Data9˜Data13 are new data.
Please refer to FIG. 2B. The controller 101 selects the third block (Block_3) as the open block, and programs the Data8′, Data2′, Data9 and Data10 into the third block (Block_3). As the third block (Block_3) is occupied by the data, the controller 101 selects the fourth block (Block_4) as the open block, and programs the data Data11, Data7′, Data12 and Data13 into the fourth block (Block_4). And then, the old data Data2, Data7 and Data8 will be considered as invalid data, which are indicated as oblique lines.
Then, the host 12 intends to output the write data Data14, Data3′, Data7″ and Data12′ to the flash memory 105. The write data Data3′, Data7″ and Data12′ are updated data of the data Data3, Data7′ and Data12, respectively. The write data Data14 is a new data.
Please refer to FIG. 2C. The controller 101 selects the fifth block (Block_5) as the open block, and programs the Data14, Data3′, Data7″ and Data12′ into the fifth block (Block_5). And then, the old data Data3, Data7′ and Data12 will be considered as invalid data, which are indicated as oblique lines.
From the above discussions, after many program actions, the flash memory 105 may contain a great number of invalid data. Consequently, the writable space of the flash memory gradually decreases. Moreover, the erase operation of the flash memory 105 can be performed in a block-wise fashion. Although the flash memory 105 as shown in FIG. 2C has many invalid data, some blocks still contain valid data. In other words, the block containing the valid data cannot be directly erased by the controlling unit 101.
As the number of free blocks in the flash memory 105 gradually decreases, it is necessary for the controller 101 of the solid state drive 10 to perform a garbage collection. After the garbage collection is performed, the storing space of the invalid data in the used blocks can be released. Consequently, the writable space of the flash memory 105 increases.
Generally, when the host 12 issues a write command, the write command may be determined as a sequential write command or a random write command according to the logical block address (LBA) from the host 12. For example, if the LBA in the write command is a consecutive logical block address, the write command from the host 12 is determined as the sequential write command. Moreover, according to the sequential write command, the write data from the host 12 is continuously stored into the flash memory 105. For example, the host 12 will continuously overwrite the flash memory 105 or continuously update the data. Hereinafter, the operations of the garbage collection of the conventional flash memory after the situation of FIG. 2C will be illustrated.
FIGS. 3A-3F schematically illustrate a data programming method comprising the garbage collection according to the prior art. For example, the controller 101 intends to release the storing space of the invalid data from the first block (Block_1) and the second block (Block_2). Please refer to FIG. 3A. The valid data Data1, Data4, Data5 and Data6 in the first block (Block_1) and the second block (Block_2) are moved to the buffer 107 by the controller 101. And then, the data Data1, Data4, Data5 and Data6 in the first block (Block_1) and the second block (Block_2) will be considered as invalid data, which are indicated as oblique lines.
While the valid data in the to-be-released blocks are moved by the controller 101, the write data from the host 12 may be continuously received by the buffer 107. In other words, the controller 101 can simultaneously perform the garbage collection and receive the write data from the host 12. As shown in FIG. 3A, the buffer 107 contains the valid data Data1, Data4, Data5 and Data6 of the first block (Block_1) and the second block (Block_2) and the write data Data15, Data16, Data17 and Data18 from the host 12. The write data Data15, Data16, Data17 and Data18 are sequential write data.
As shown in FIG. 3B, the controller 101 confirms that no valid data are contained in the first block (Block_1) and the second block (Block_2). Then, the controller 101 performs a block erase operation on the first block (Block_1) and the second block (Block_2). Consequently, the first block (Block_1) and the second block (Block_2) are erased as free blocks.
Then, as shown in FIG. 3C, the controller 101 performs the program action to program the data of the buffer 107 into the flash memory 105. Consequently, one programming procedure comprising the garbage collection is completed. That is, the controller 101 firstly selects the first block (Block_1) as the open block, and programs the data Data1, Data15, Data4 and Data16 into the first block (Block_1). Then, the controller 101 selects the second block (Block_2) as the open block, and programs the data Data17, Data5, Data6 and Data18 into the second block (Block_2).
While the controller 101 performs the programming procedure comprising the garbage collection, if the block to be erased contains the valid data and the invalid data, the controller 101 has to move the valid data from the block to the buffer 107, and the controller 101 has to receive the write data from the host 12 and temporarily store the write data into the buffer 107. In other words, while the controller 101 performs the programming procedure comprising the garbage collection, the moved valid data corresponding to the garbage collection and the write data from the host 12 are temporarily stored in the buffer 107 in an interlaced manner. Consequently, after the data in the buffer 107 are programmed to the open blocks of the flash memory 105 by the controller 101, the moved valid data corresponding to the garbage collection and the write data from the host 12 are stored into the first block (Block_1) and the second block (Block_2) in the interlaced manner.
Please refer to FIG. 3C again. If the storing space of the flash memory 105 is insufficient, the controller 101 has to re-perform the garbage collection in order to program the new or updated data. For example, the host 12 intends to program the write data Data15′, Data16′, Data17′ and Data18′ to the flash memory 105. The write data Data15′, Data16′, Data17′ and Data18′ are sequential write data. In addition, the write data Data15′, Data16′, Data17′ and Data18′ are updated data of the data Data15, Data16, Data17 and Data18, respectively. As shown in FIG. 3C, the old data Data15, Data16, Data17 and Data18 in the first block (Block_1) and the second block (Block_2) will be considered as the invalid data because these data have been updated. However, since the moved valid data corresponding to the garbage collection are still stored in the first block (Block_1) and the second block (Block_2), the controller 101 has to re-perform the garbage collection in order to move these valid data to the buffer 107. Then, the controller 101 will perform a block erase operation on the first block (Block_1) and the second block (Block_2).
The process of performing another garbage collection will be illustrated with reference to FIGS. 3D-3F. Firstly, as shown in FIG. 3D, the valid data Data1, Data4, Data5 and Data6 in the first block (Block_1) and the second block (Block_2) are moved to the buffer 107 by the controller 101. And then, the data Data1, Data4, Data5 and Data6 in the first block (Block_1) and the second block (Block_2) will be considered as invalid data, which are indicated as oblique lines.
Similarly, while the valid data in the to-be-released blocks are moved by the controller 101, the write data from the host 12 are continuously received by the buffer 107. As shown in FIG. 3D, the buffer 107 contains the valid data Data1, Data4, Data5 and Data6 of the first block (Block_1) and the second block (Block_2) and the write data Data15′, Data16′, Data17′ and Data18′ from the host 12. And then, the old data Data15, Data16, Data17 and Data18 in the first block (Block_1) and the second block (Block_2) will be considered as the invalid data because these data have been updated.
As shown in FIG. 3E, the controller 101 confirms that no valid data are contained in the first block (Block_1) and the second block (Block_2). Then, the controller 101 performs a block erase operation on the first block (Block_1) and the second block (Block_2). Consequently, the first block (Block_1) and the second block (Block_2) are erased as free blocks.
Then, as shown in FIG. 3F, the controller 101 performs the program action to program the data of the buffer 107 into the flash memory 105. Consequently, another programming procedure comprising the garbage collection is completed. That is, the controller 101 firstly selects the first block (Block_1) as the open block, and programs the data Data1, Data15′, Data16′ and Data4 into the first block (Block_1). Then, the controller 101 selects the second block (Block_2) as the open block, and programs the data Data17′, Data18′, Data5 and Data6 into the second block (Block_2).
Similarly, after the data in the buffer 107 are programmed to the open blocks of the flash memory 105 by the controller 101, the moved valid data corresponding to the garbage collection and the write data from the host 12 are stored into the first block (Block_1) and the second block (Block_2) in the interlaced manner (see FIG. 3F).
Please refer to FIG. 3F again. If the storing space of the flash memory 105 is insufficient and the host 12 intends to update or overwrite the sequential write data Data15′, Data16′, Data17′ and Data18′, the controller 101 has to re-perform the garbage collection and repeatedly move the valid data corresponding to the previous garbage collection. The procedures are similar to those mentioned above, and are not redundantly described herein.
FIG. 4 schematically illustrates the data storage conditions in the flash memory of the conventional solid state drive. According to the above data programming method, each of the blocks Block_1˜Block_n of the flash memory 105 may contain the moved valid data (GC) corresponding to the garbage collection and the write data (H) from the host 12 after the programming procedure comprising the garbage collection is completed many times.
For example, after the above data programming method, the data in the flash memory 105 of the conventional solid state drive 10 has the storage condition as shown in FIG. 4. If the host 12 issues a sequential write command, the controller 101 has to continuously re-perform the garbage collection and repeatedly move the valid data corresponding to the previous garbage collection. Consequently, free blocks are generated. Moreover, the open blocks also store the moved valid data (GC) corresponding to the garbage collection and the write data (H) from the host 12. Under this circumstance, the write speed of the solid state drive 10 decreases and fails to be effectively increased.
From the above discussions about the conventional data programming method, the moved valid data (GC) corresponding to the garbage collection and the write data (H) from the host 12 are stored in the flash memory 105 in the interlaced manner. Moreover, if the host 12 intends to update or overwrite the sequential write data, the controller 101 has to re-perform the garbage collection and repeatedly move the valid data corresponding to the previous garbage collection. Moreover, after the valid data in the to-be-released blocks are moved to the buffer 107, the controller 101 performs the block erase operation and programs the data into the flash memory 105. Moreover, since the buffer 107 still contains the valid data (GC) and the write data (H) in the interlaced manner, the valid data (GC) and the write data (H) are programmed into the open block in the interlaced manner.
During the sequential write process, the controller 101 has to continuously re-perform the garbage collection and repeatedly move the valid data corresponding to the previous garbage collection. Consequently, the write speed of the solid state drive 10 fluctuates between a high speed and a low speed. That is, the write speed cannot reach the desired level.